#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

class Solution {
    public:
        string minWindow(string S, string T) {
            int needToFind[256] = {0};
            int hasFind[256] = {0};
            for (int i = 0; i < T.size(); i++)
                needToFind[T[i]]++;

            int len = S.size(), count = 0, start = 0;
            string str;
            for (int i = 0; i < S.size(); i++) {
                if (needToFind[S[i]] == 0) 
                     continue;
                hasFind[S[i]]++;
                if (hasFind[S[i]] <= needToFind[S[i]]) 
                    count++;
                if (count == T.size()) {
                    while (needToFind[S[start]] == 0 || hasFind[S[start]] > needToFind[S[start]]) {
                       if ( hasFind[S[start]] > needToFind[S[start]]) {
                           hasFind[S[start]]--;
                       }
                       start++;
                    } 
                    if (count < T.size()) continue;
                    int curSize = i - start +1;
                    if (curSize <= len) {
                        len = curSize;
                        str = S.substr(start, i-start+1);
                    }
                }
            }
            return str;
        }
};

//add better code
    string minWindow(string S, string T) {
        int needToFind[256] = {0}, hasFind[256] = {0};
        for (int i = 0; i < T.size(); i++) {
            needToFind[T[i]]++;
        }   
        string str;
        int start = 0, cnt = 0;
        for (int i = 0; i < S.size(); i++) {
            if (needToFind[S[i]] == 0) continue;
            if (hasFind[S[i]] < needToFind[S[i]]) {
                cnt++;
            }   
            hasFind[S[i]]++;
            while(needToFind[S[start]] == 0 || (needToFind[S[start]] < hasFind[S[start]])) {hasFind[S[start]]--; start++;}
            if (cnt >= T.size()) {
                if (str.size() == 0 || (str.size() > 0 &&  (i - start + 1 < str.size()))) 
                    str = S.substr(start, i - start +1);
            }   
        }   
        return str;
    } 


int main(int argc, char **argv)
{
    Solution mySolution;

    cout << "-----------------Test 1--------------------" << endl;
    mySolution.minWindow("ADOBECODEBANC", "ABC");


    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
